#include <iostream>
#include <string>

using namespace std;

int *buildNext(string &pat) //next 数组的生成
{
    int m = pat.size();
    int j = 0;
    int *N = new int[m];
    int t = N[0] = -1;  //哨兵
    while (j < m - 1)
    {
        if (t < 0 || pat[j] == pat[t])
            N[++j] = ++t;
        else
            t = N[t];
    }
    return N;
}

int kmp_match(string tex, string pat)
{
    int *next = buildNext(pat);

    int n = tex.length();
    int i = 0;

    int m = pat.length();
    int j = 0;

    while (j < m && i < n)
    {
        if (j == -1 || tex[i] == pat[j]) //匹配 检测下一个字符
        {
            i++;
            j++;
        }
        else //不匹配 则复位
        {
            j = next[j];
        }
    }
    delete[] next;
    return i - j;
}

int main()
{
    string text = "asdfddg";
    string pattern = "ddd";

    int f = kmp_match(text,pattern);
    (f <= text.length() - pattern.length()) ? cout << "true" << endl : cout << "false" << endl;
    return 0;
}